<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <link rel="stylesheet" href="../../aosa.css" type="text/css">
    <title>The Performance of Open Source Software: Warp</title>
  </head>
  <body>

    <div class="titlebox">
      <h1>The Performance of Open Source Applications<br>Warp</h1>
      <p class="author">Kazu Yamamoto, Michael Snoyman, and Andreas Voellmy</p>
    </div>

<p>Warp is a high-performance <span class="caps">HTTP</span> server library written in Haskell, a purely functional programming language. Both Yesod, a web application framework, and <code>mighty</code>, an <span class="caps">HTTP</span> server, are implemented over Warp. According to our throughput benchmark, <code>mighty</code> provides performance on a par with <code>nginx</code>. This article will explain the architecture of Warp and how we achieved its performance. Warp can run on many platforms, including Linux, <span class="caps">BSD</span> variants, Mac <span class="caps">OS</span>, and Windows. To simplify our explanation, however, we will only talk about Linux for the remainder of this article.</p>

<h2 id="network-programming-in-haskell">Network Programming in Haskell</h2>

<p>Some people believe that functional programming languages are slow or impractical. However, to the best of our knowledge, Haskell provides a nearly ideal approach for network programming. This is because the Glasgow Haskell Compiler (<span class="caps">GHC</span>), the flagship compiler for Haskell, provides lightweight and robust user threads (sometimes called green threads). In this section, we briefly review some well-known approaches to server-side network programming and compare them with network programming in Haskell. We demonstrate that Haskell offers a combination of programmability and performance not available in other approaches: Haskell's convenient abstractions allow programmers to write clear, simple code, while <span class="caps">GHC</span>'s sophisticated compiler and multi-core run-time system produce multi-core programs that execute in a way very similar to the most advanced hand-crafted network programs.</p>

<h3 id="native-threads">Native Threads</h3>

<p>Traditional servers use a technique called thread programming. In this architecture, each connection is handled by a single process or native thread (sometimes called an <span class="caps">OS</span> thread).</p>

<p>This architecture can be further segmented based on the mechanism used for creating the processes or native threads. When using a thread pool, multiple processes or native threads are created in advance. An example of this is the prefork mode in Apache. Otherwise, a process or native thread is spawned each time a connection is received. <a href="#figure-11.1">Figure 11.1</a> illustrates this.</p>

<div class="center figure">
<a name="figure-11.1"></a><img src="warp-images/1.png" alt="Figure 11.1 - Native threads" title="Figure 11.1 - Native threads" />
</div>

<p class="center figcaption">
<small>Figure 11.1 - Native threads</small>
</p>

<p>The advantage of this architecture is that it enables developers to write clear code. In particular, the use of threads allows the code to follow a simple and familiar flow of control and to use simple procedure calls to fetch input or send output. Also, because the kernel assigns processes or native threads to available cores, we can balance utilization of cores. Its disadvantage is that a large number of context switches between kernel and processes or native threads occur, resulting in performance degradation.</p>

<h3 id="event-driven-architecture">Event-driven Architecture</h3>

<p>In the world of high-performance servers, the recent trend has been to take advantage of event-driven programming. In this architecture multiple connections are handled by a single process (<a href="#figure-11.2">Figure 11.2</a>). Lighttpd is an example of a web server using this architecture.</p>

<div class="center figure">
<a name="figure-11.2"></a><img src="warp-images/2.png" alt="Figure 11.2 - Event-driven architecture" title="Figure 11.2 - Event-driven architecture" />
</div>

<p class="center figcaption">
<small>Figure 11.2 - Event-driven architecture</small>
</p>

<p>Since there is no need to switch processes, fewer context switches occur, and performance is thereby improved. This is its chief advantage.</p>

<p>On the other hand, this architecture substantially complicates the network program. In particular, this architecture inverts the flow of control so that the event loop controls the overall execution of the program. Programmers must therefore restructure their program into event handlers, each of which execute only non-blocking code. This restriction prevents programmers from performing I/O using procedure calls; instead more complicated asynchronous methods must be used. Along the same lines, conventional exception handling methods are no longer applicable.</p>

<h3 id="one-process-per-core">One Process Per Core</h3>

<p>Many have hit upon the idea of creating N event-driven processes to utilize N cores (<a href="#figure-11.3">Figure 11.3</a>). Each process is called a <em>worker</em>. A service port must be shared among workers. Using the prefork technique, port sharing can be achieved.</p>

<p>In traditional process programming, a process for a new connection is forked after the connection is accepted. In contrast, the prefork technique forks processes before new connections are accepted. Despite the shared name, this technique should not be confused with Apache's prefork mode.</p>

<div class="center figure">
<a name="figure-11.3"></a><img src="warp-images/3.png" alt="Figure 11.3 - One process per core" title="Figure 11.3 - One process per core" />
</div>

<p class="center figcaption">
<small>Figure 11.3 - One process per core</small>
</p>

<p>One web server that uses this architecture is <code>nginx</code>. Node.js used the event-driven architecture in the past, but recently it also implemented the prefork technique. The advantage of this architecture is that it utilizes all cores and improves performance. However, it does not resolve the issue of programs having poor clarity, due to the reliance on handler and callback functions.</p>

<h3 id="user-threads">User Threads</h3>

<p><span class="caps">GHC</span>'s user threads can be used to help solve the code clarity issue. In particular, we can handle each <span class="caps">HTTP</span> connection in a new user thread. This thread is programmed in a traditional style, using logically blocking I/O calls. This keeps the program clear and simple, while <span class="caps">GHC</span> handles the complexities of non-blocking I/O and multi-core work dispatching.</p>

<p>Under the hood, <span class="caps">GHC</span> multiplexes user threads over a small number of native threads. <span class="caps">GHC</span>'s run-time system includes a multi-core thread scheduler that can switch between user threads cheaply, since it does so without involving any <span class="caps">OS</span> context switches.</p>

<p><span class="caps">GHC</span>'s user threads are lightweight; modern computers can run 100,000 user threads smoothly. They are robust; even asynchronous exceptions are caught (this feature is used by the timeout handler, described in <a href="#sec.warp.arch">Warp's Architecture</a> and in <a href="#sec.warp.timers">Timers for File Descriptors</a>.) In addition, the scheduler includes a multi-core load balancing algorithm to help utilize capacity of all available cores.</p>

<p>When a user thread performs a logically blocking I/O operation, such as receiving or sending data on a socket, a non-blocking call is actually attempted. If it succeeds, the thread continues immediately without involving the I/O manager or the thread scheduler. If the call would block, the thread instead registers interest for the relevant event with the run-time system's I/O manager component and then indicates to the scheduler that it is waiting. Independently, an I/O manager thread monitors events and notifies threads when their events occur, causing them to be re-scheduled for execution. This all happens transparently to the user thread, with no effort on the Haskell programmer's part.</p>

<p>In Haskell, most computation is non-destructive. This means that almost all functions are thread-safe. <span class="caps">GHC</span> uses data allocation as a safe point to switch context of user threads. Because of functional programming style, new data are frequently created and it is known that <a href="http://www.aosabook.org/en/ghc.html">such data allocation occurs regularly enough for context switching</a>.</p>

<p>Though some languages provided user threads in the past, they are not commonly used now because they were not lightweight or were not robust. Note that some languages provide library-level coroutines but they are not preemptive threads. Note also that Erlang and Go provide lightweight processes and lightweight goroutines, respectively.</p>

<p>As of this writing, <code>mighty</code> uses the prefork technique to fork processes in order to use more cores. (Warp does not have this functionality.) <a href="#figure-11.4">Figure 11.4</a> illustrates this arrangement in the context of a web server with the prefork technique written in Haskell, where each browser connection is handled by a single user thread, and a single native thread in a process running on a <span class="caps">CPU</span> core handles work from several connections.</p>

<div class="center figure">
<a name="figure-11.4"></a><img src="warp-images/4.png" alt="Figure 11.4 - User threads with one process per core" title="Figure 11.4 - User threads with one process per core" />
</div>

<p class="center figcaption">
<small>Figure 11.4 - User threads with one process per core</small>
</p>

<p>We found that the I/O manager component of the <span class="caps">GHC</span> run-time system itself has performance bottlenecks. To solve this problem, we developed a <em>parallel I/O manager</em> that uses per-core event registration tables and event monitors to greatly improve multi-core scaling. A Haskell program with the parallel I/O manager is executed as a single process and multiple I/O managers run as native threads to use multiple cores (<a href="#figure-11.5">Figure 11.5</a>). Each user thread is executed on any one of the cores.</p>

<div class="center figure">
<a name="figure-11.5"></a><img src="warp-images/5.png" alt="Figure 11.5 - User threads in a single process" title="Figure 11.5 - User threads in a single process" />
</div>

<p class="center figcaption">
<small>Figure 11.5 - User threads in a single process</small>
</p>

<p><span class="caps">GHC</span> version 7.8–which includes the parallel I/O manager–will be released in the autumn of 2013. With <span class="caps">GHC</span> version 7.8, Warp itself will be able to use this architecture without any modifications and <code>mighty</code> will not need to use the prefork technique.</p>

<h2 id="warps-architecture">Warp's Architecture</h2>

<p><a name="sec.warp.arch"> </a></p>

<p>Warp is an <span class="caps">HTTP</span> engine for the Web Application Interface (<span class="caps">WAI</span>). It runs <span class="caps">WAI</span> applications over <span class="caps">HTTP</span>. As we described above, both Yesod and <code>mighty</code> are examples of <span class="caps">WAI</span> applications, as illustrated in <a href="#figure-11.6">Figure 11.6</a>.</p>

<div class="center figure">
<a name="figure-11.6"></a><img src="warp-images/wai.png" alt="Figure 11.6 - Web Application Interface (WAI)" title="Figure 11.6 - Web Application Interface (WAI)" />
</div>

<p class="center figcaption">
<small>Figure 11.6 - Web Application Interface (<span class="caps">WAI</span>)</small>
</p>

<p>The type of a <span class="caps">WAI</span> application is as follows:</p>

<pre><code>type Application = Request -&gt; ResourceT IO Response</code></pre>

<p>In Haskell, argument types of functions are separated by right arrows and the rightmost one is the type of the return value. So, we can interpret the definition as: a <span class="caps">WAI</span> <code>Application</code> takes a <code>Request</code> and returns a <code>Response</code>, used in the context where I/O is possible and resources are well managed.</p>

<p>After accepting a new <span class="caps">HTTP</span> connection, a dedicated user thread is spawned for the connection. It first receives an <span class="caps">HTTP</span> request from a client and parses it to <code>Request</code>. Then, Warp gives the <code>Request</code> to the <span class="caps">WAI</span> application and receives a <code>Response</code> from it. Finally, Warp builds an <span class="caps">HTTP</span> response based on the <code>Response</code> value and sends it back to the client. This is illustrated in <a href="#figure-11.7">Figure 11.7</a>.</p>

<div class="center figure">
<a name="figure-11.7"></a><img src="warp-images/warp.png" alt="Figure 11.7 - The architecture of Warp" title="Figure 11.7 - The architecture of Warp" />
</div>

<p class="center figcaption">
<small>Figure 11.7 - The architecture of Warp</small>
</p>

<p>The user thread repeats this procedure as necessary and terminates itself when the connection is closed by the peer or an invalid request is received. The thread also terminates if a significant amount of data is not received after a certain period of time (i.e., a timeout has occurred).</p>

<h2 id="the-performance-of-warp">The Performance of Warp</h2>

<p>Before we explain how to improve the performance of Warp, we would like to show the results of our benchmark. We measured throughput of <code>mighty</code> version 2.8.4 (with Warp version 1.3.8.1) and <code>nginx</code> version 1.4.0. Our benchmark environment is as follows:</p>

<ul>
<li>Two "12 core" machines (Intel Xeon E5645, two sockets, 6 cores per 1 <span class="caps">CPU</span>) connected with 1 gbps Ethernet.</li>
<li>One machine directly runs Linux version 3.2.0 (Ubuntu 12.04 <span class="caps">LTS</span>).</li>
<li>The other directly runs FreeBSD 9.1.</li>
</ul>

<p>We tested several benchmark tools in the past and our favorite one was <code>httperf</code>. Since it uses <code>select()</code> and is just a single process program, it reaches its performance limits when we try to measure <span class="caps">HTTP</span> servers on multi-core machines. So, we switched to <code>weighttp</code>, which is based on <code>libev</code> (the <code>epoll</code> family) and can use multiple native threads. We used <code>weighttp</code> from FreeBSD as follows:</p>

<pre><code>weighttp -n 100000 -c 1000 -t 10 -k http://&lt;ip_address&gt;:&lt;port_number&gt;/</code></pre>

<p>This means that 1,000 <span class="caps">HTTP</span> connections are established, with each connection sending 100 requests. 10 native threads are spawned to carry out these jobs.</p>

<p>The target web servers were compiled on Linux. For all requests, the same <code>index.html</code> file is returned. We used <code>nginx</code>&#8216;s <code>index.html</code>, whose size is 151 bytes.</p>

<p>Since Linux/FreeBSD have many control parameters, we need to configure the parameters carefully. You can find a good introduction to Linux parameter tuning in <a href="http://gwan.com/en_apachebench_httperf.html">ApacheBench <span class="amp">&amp;</span> HTTPerf</a>. We carefully configured both <code>mighty</code> and <code>nginx</code> as follows:</p>

<ul>
<li>enabled file descriptor cache</li>
<li>disabled logging</li>
<li>disabled rate limitation</li>
</ul>

<p>Here is the result:</p>

<div class="center figure">
<a name="figure-11.8"></a><img src="warp-images/benchmark.png" alt="Figure 11.8 - Performance of Warp and \code{nginx}" title="Figure 11.8 - Performance of Warp and \code{nginx}" />
</div>

<p class="center figcaption">
<small>Figure 11.8 - Performance of Warp and </small>
</p>

<p>The x-axis is the number of workers and the y-axis gives throughput, measured in requests per second.</p>

<ul>
<li>mighty 2.8.4 (<span class="caps">GHC</span> 7.7): compiled with <span class="caps">GHC</span> version 7.7.20130504 (to be <span class="caps">GHC</span> version 7.8). It uses the parallel I/O manager with only one worker. <span class="caps">GHC</span> run-time option, <code>+RTS -qa -A128m -N&lt;x&gt;</code> is specified where <code>&lt;x&gt;</code> is the number of cores and <code>128m</code> is the allocation area size used by the garbage collector.</li>
<li>mighty 2.8.4 (<span class="caps">GHC</span> 7.6.3): compiled with <span class="caps">GHC</span> version 7.6.3 (which is the latest stable version).</li>
</ul>

<h2 id="key-ideas">Key Ideas</h2>

<p>We kept four key ideas in mind when implementing our high-performance server in Haskell:</p>

<ol style="list-style-type: decimal">
<li>Issuing as few system calls as possible</li>
<li>Using specialized function implementations and avoiding recalculation</li>
<li>Avoiding locks</li>
<li>Using proper data structures</li>
</ol>

<h3 id="issuing-as-few-system-calls-as-possible">Issuing as Few System Calls as Possible</h3>

<p>Although system calls are typically inexpensive on most modern operating systems, they can add a significant computational burden when called frequently. Indeed, Warp performs several system calls when serving each request, including <code>recv()</code>, <code>send()</code> and <code>sendfile()</code> (a system call that allows zero-copying a file). Other system calls, such as <code>open()</code>, <code>stat()</code> and <code>close()</code> can often be omitted when processing a single request, thanks to a cache mechanism described in <a href="#sec.warp.timers">Timers for File Descriptors</a>.</p>

<p>We can use the <code>strace</code> command to see what system calls are actually used. When we observed the behavior of <code>nginx</code> with <code>strace</code>, we noticed that it used <code>accept4()</code>, which we did not know about at the time.</p>

<p>Using Haskell's standard network library, a listening socket is created with the non-blocking flag set. When a new connection is accepted from the listening socket, it is necessary to set the corresponding socket as non-blocking as well. The network library implements this by calling <code>fcntl()</code> twice: once to get the current flags and twice to set the flags with the non-blocking flag enabled.</p>

<p>On Linux, the non-blocking flag of a connected socket is always unset even if its listening socket is non-blocking. The system call <code>accept4()</code> is an extension version of <code>accept()</code> on Linux. It can set the non-blocking flag when accepting. So, if we use <code>accept4()</code>, we can avoid two unnecessary calls to <code>fcntl()</code>. Our patch to use <code>accept4()</code> on Linux has been already merged to the network library.</p>

<h3 id="specialized-functions-and-avoiding-recalculation">Specialized Functions and Avoiding Recalculation</h3>

<p><span class="caps">GHC</span> provides a profiling mechanism, but it has a limitation: correct profiling is only possible if a program runs in the foreground and does not spawn child processes. If we want to profile live activities of servers, we need to take special care.</p>

<p><code>mighty</code> has this mechanism. Suppose that N is the number of workers in the configuration file of <code>mighty</code>. If N is greater than or equal to 2, <code>mighty</code> creates N child processes and the parent process just works to deliver signals. However, if N is 1, <code>mighty</code> does not create any child process. Instead, the executed process itself serves <span class="caps">HTTP</span>. Also, <code>mighty</code> stays in its terminal if debug mode is on.</p>

<p>When we profiled <code>mighty</code>, we were surprised that the standard function to format date strings consumed the majority of <span class="caps">CPU</span> time. As many know, an <span class="caps">HTTP</span> server should return <span class="caps">GMT</span> date strings in header fields such as <code>Date</code>, <code>Last-Modified</code>, etc.:</p>

<pre><code>Date: Mon, 01 Oct 2012 07:38:50 GMT</code></pre>

<p>So, we implemented a special formatter to generate <span class="caps">GMT</span> date strings. A comparison of our specialized function and the standard Haskell implementation using the <code>criterion</code> benchmark library showed that ours was much faster. But if an <span class="caps">HTTP</span> server accepts more than one request per second, the server repeats the same formatting again and again. So, we also implemented a cache mechanism for date strings.</p>

<p>We also explain specialization and avoiding recalculation in <a href="#sec.warp.writingparser">Writing the Parser</a> and <a href="#sec.warp.composer">Composer for <span class="caps">HTTP</span> Response Header</a>.</p>

<h3 id="avoiding-locks">Avoiding Locks</h3>

<p>Unnecessary locks are evil for programming. Our code sometimes uses unnecessary locks imperceptibly because, internally, the run-time systems or libraries use locks. To implement high-performance servers, we need to identify such locks and avoid them if possible. It is worth pointing out that locks will become much more critical under the parallel I/O manager. We will talk about how to identify and avoid locks in <a href="#sec.warp.connectiontimers">Timers for Connections</a> and <a href="#sec.warp.memory">Memory Allocation</a>.</p>

<h3 id="using-proper-data-structures">Using Proper Data Structures</h3>

<p>Haskell's standard data structure for strings is <code>String</code>, which is a linked list of Unicode characters. Since list programming is the heart of functional programming, <code>String</code> is convenient for many purposes. But for high-performance servers, the list structure is too slow and Unicode is too complex since the <span class="caps">HTTP</span> protocol is based on <em>byte</em> streams. Instead, we use <code>ByteString</code> to express strings (or buffers). A <code>ByteString</code> is an array of bytes with metadata. Thanks to this metadata, splicing without copying is possible. This is described in detail in <a href="#sec.warp.writingparser">Writing the Parser</a>.</p>

<p>Other examples of proper data structures are <code>Builder</code> and double <code>IORef</code>. They are explained in <a href="#sec.warp.composer">Composer for <span class="caps">HTTP</span> Response Header</a> and <a href="#sec.warp.connectiontimers">Timers for Connections</a>, respectively.</p>

<h2 id="http-request-parser"><span class="caps">HTTP</span> Request Parser</h2>

<p>Besides the many issues involved with efficient concurrency and I/O in a multi-core environment, Warp also needs to be certain that each core is performing its tasks efficiently. In that regard, the most relevant component is the <span class="caps">HTTP</span> request processor. Its purpose is to take a stream of bytes coming from the incoming socket, parse out the request line and individual headers, and leave the request body to be processed by the application. It must take this information and produce a data structure which the application (whether a Yesod application, <code>mighty</code>, or something else) will use to form its response.</p>

<p>The request body itself presents some interesting challenges. Warp provides full support for pipelining and chunked request bodies. As a result, Warp must "dechunk" any chunked request bodies before passing them to the application. With pipelining, multiple requests can be transferred on a single connection. Therefore, Warp must ensure that the application does not consume too many bytes, as that would remove vital information from the next request. It must also be sure to discard any data remaining from the request body; otherwise, the remainder will be parsed as the beginning of the next request, causing either an invalid request or a misunderstood request.</p>

<p>As an example, consider the following theoretical request from a client:</p>

<pre><code>POST /some/path HTTP/1.1
Transfer-Encoding: chunked
Content-Type: application/x-www-form-urlencoded

0008
message=
000a
helloworld
0000

GET / HTTP/1.1</code></pre>

<p>The <span class="caps">HTTP</span> parser must extract the <code>/some/path</code> pathname and the <code>Content-Type</code> header and pass these to the application. When the application begins reading the request body, it must strip off the chunk headers (e.g., <code>0008</code> and <code>000a</code>) and instead provide the actual content, i.e., <code>message=helloworld</code>. It must also ensure that no more bytes are consumed after the chunk terminator (<code>0000</code>) so as to not interfere with the next pipelined request.</p>

<h3 id="writing-the-parser">Writing the Parser</h3>

<p><a name="sec.warp.writingparser"> </a></p>

<p>Haskell is known for its powerful parsing capabilities. It has traditional parser generators as well as combinator libraries, such as Parsec and Attoparsec. Parsec and Attoparsec's textual modules work in a fully Unicode-aware manner. However, <span class="caps">HTTP</span> headers are guaranteed to be <span class="caps">ASCII</span>, so Unicode awareness is an overhead we need not incur.</p>

<p>Attoparsec also provides a binary interface for parsing, which would let us bypass the Unicode overhead. But as efficient as Attoparsec is, it still introduces an overhead relative to a hand-rolled parser. So for Warp, we have not used any parser libraries. Instead, we perform all parsing manually.</p>

<p>This gives rise to another question: how do we represent the actual binary data? The answer is a <code>ByteString</code>, which is essentially three pieces of data: a pointer to some piece of memory, the offset from the beginning of that memory to the data in question, and the size of our data.</p>

<p>The offset information may seem redundant. We could instead insist that our memory pointer point to the beginning of our data. However, by including the offset, we enable data sharing. Multiple <code>ByteString</code>s can all point to the same chunk of memory and use different parts of it (also known as <em>splicing</em>). There is no worry of data corruption, since <code>ByteString</code>s (like most Haskell data) are immutable. When the final pointer to a piece of memory is no longer used, then the memory buffer is deallocated.</p>

<p>This combination is perfect for our use case. When a client sends a request over a socket, Warp will read the data in relatively large chunks (currently 4096 bytes). In most cases, this is large enough to encompass the entire request line and all request headers. Warp will then use its hand-rolled parser to break this large chunk into lines. This can be done efficiently for the following reasons:</p>

<ol style="list-style-type: decimal">
<li><p>We need only scan the memory buffer for newline characters. The bytestring library provides such helper functions, which are implemented with lower-level C functions like <code>memchr</code>. (It's actually a little more complicated than that due to multiline headers, but the same basic approach still applies.)</p></li>
<li><p>There is no need to allocate extra memory buffers to hold the data. We just take splices from the original buffer. See <a href="#figure-11.9">Figure 11.9</a> for a demonstration of splicing individual components from a larger chunk of data. It's worth stressing this point: we actually end up with a situation which is more efficient than idiomatic C. In C, strings are null-terminated, so splicing requires allocating a new memory buffer, copying the data from the old buffer, and appending the null character.</p></li>
</ol>

<div class="center figure">
<a name="figure-11.9"></a><img src="warp-images/bytestring.png" alt="Figure 11.9 - Splicing ByteStrings" title="Figure 11.9 - Splicing ByteStrings" />
</div>

<p class="center figcaption">
<small>Figure 11.9 - Splicing ByteStrings</small>
</p>

<p>Once the buffer has been broken into lines, we perform a similar maneuver to turn the header lines into key/value pairs. For the request line, we parse the requested path fairly deeply. Suppose we have a request for:</p>

<pre><code>GET /buenos/d%C3%ADas HTTP/1.1</code></pre>

<p>In this case, we would need to perform the following steps:</p>

<ol style="list-style-type: decimal">
<li>Separate the request method, path, and version into individual pieces.</li>
<li>Tokenize the path along forward slashes, ending up with <code>[&quot;buenos&quot;, &quot;d%C3%ADas&quot;]</code>.</li>
<li>Percent-decode the individual pieces, ending up with <code>[&quot;buenos&quot;, &quot;d\195\173as&quot;]</code>.</li>
<li><span class="caps">UTF8</span>-decode each piece, finally arriving at Unicode-aware text: <code>[&quot;buenos&quot;, &quot;días&quot;]</code>.</li>
</ol>

<p>There are a few performance gains we achieve with this process:</p>

<ol style="list-style-type: decimal">
<li>As with newline checking, finding forward slashes is a very efficient operation.</li>
<li>We use an efficient lookup table for turning the Hex characters into numerical values. This code is a single memory lookup and involves no branching.</li>
<li><span class="caps">UTF8</span>-decoding is a highly optimized operation in the text package. Likewise, the text package represents this data in an efficient, packed representation.</li>
<li>Due to Haskell's laziness, this calculation will be performed on demand. If the application in question does not need the textual version of the path, none of these steps will be performed.</li>
</ol>

<p>The final piece of parsing we perform is dechunking. In many ways, dechunking is a simpler form of parsing. We parse a single Hex number, and then read the stated number of bytes. Those bytes are passed on verbatim (/without any buffer copying) to the application.</p>

<h3 id="conduit">Conduit</h3>

<p>This article has mentioned a few times the concept of passing the request body to the application. It has also hinted at the issue of the application passing a response back to the server, and the server receiving data from and sending data to the socket. A final related point not yet discussed is <em>middleware</em>, which are components sitting between the server and application that modify the request or response. The definition of a middleware is:</p>

<pre><code>type Middleware = Application -&gt; Application</code></pre>

<p>The intuition behind this is that a middleware will take some "internal" application, preprocess the request, pass it to the internal application to get a response, and then postprocess the response. For our purposes, a good example would be a gzip middleware, which automatically compresses response bodies.</p>

<p>A prerequisite for the creation of such middlewares is a means of modifying both incoming and outgoing data streams. A standard approach historically in the Haskell world has been <em>lazy I/O</em>. With lazy I/O, we represent a stream of values as a single, pure data structure. As more data is requested from this structure, I/O actions are performed to grab the data from its source. Lazy I/O provides a huge level of composability. However, for a high-throughput server, it presents a major obstacle: resource finalization in lazy I/O is non-deterministic. Using lazy I/O, it would be easy for a server under high load to quickly run out of file descriptors.</p>

<p>It would also be possible to use a lower-level abstraction, essentially dealing directly with read and write functions. However, one of the advantages of Haskell is its high-level approach, allowing us to reason about the behavior of our code. It's also not obvious how such a solution would deal with some of the common issues which arise when creating web applications. For example, it's often necessary to have a buffering solution, where we read a certain amount of data at one step (/e.g., the request header processing), and read the remainder in a separate part of the code base (e.g., the web application).</p>

<p>To address this dilemma, the <span class="caps">WAI</span> protocol (and therefore Warp) is built on top of the conduit package. This package provides an abstraction for streams of data. It keeps much of the composability of lazy I/O, provides a buffering solution, and guarantees deterministic resource handling. Exceptions are also kept where they belong, in the parts of your code which deal with I/O, instead of hiding them in a data structure claiming to be pure.</p>

<p>Warp represents the incoming stream of bytes from the client as a <code>Source</code>, and writes data to be sent to the client to a <code>Sink</code>. The <code>Application</code> is provided a <code>Source</code> with the request body, and provides a response as a <code>Source</code> as well. Middlewares are able to intercept the <code>Source</code>s for the request and response bodies and apply transformations to them. <a href="#figure-11.10">Figure 11.10</a> demonstrates how a middleware fits between Warp and an application. The composability of the conduit package makes this an easy and efficient operation.</p>

<div class="center figure">
<a name="figure-11.10"></a><img src="warp-images/middleware.png" alt="Figure 11.10 - Middlewares" title="Figure 11.10 - Middlewares" />
</div>

<p class="center figcaption">
<small>Figure 11.10 - Middlewares</small>
</p>

<p>Elaborating on the gzip middleware example, conduit allows us to create a middleware which runs in a nearly optimal manner. The original <code>Source</code> provided by the application is connected to the <code>gzip</code> <code>Conduit</code>. As each new chunk of data is produced by the initial <code>Source</code>, it is fed into the <code>zlib</code> library, filling up a buffer with compressed bytes. When that buffer is filled, it is emitted, either to another middleware, or to Warp. Warp then takes this compressed buffer and sends it over the socket to the client. At this point, the buffer can either be reused, or its memory freed. In this way, we have optimal memory usage, do not produce any extra data in the case of network failure, and lessen the garbage collection burden for the run time system.</p>

<p>Conduit itself is a large topic, and therefore will not be covered in more depth. It would suffice to say for now that conduit's usage in Warp is a contributing factor to its high performance.</p>

<h3 id="slowloris-protection">Slowloris Protection</h3>

<p>We have one final concern: the Slowloris attack. This is a form of Denial of Service (DoS) attack wherein each client sends very small amounts of information. By doing so, the client is able to maintain a higher number of connections on the same hardware/bandwidth. Since the web server has a constant overhead for each open connection regardless of bytes being transferred, this can be an effective attack. Therefore, Warp must detect when a connection is not sending enough data over the network and kill it.</p>

<p>We discuss the timeout manager in more detail below, which is the true heart of Slowloris protection. When it comes to request processing, our only requirement is to tease the timeout handler to let it know more data has been received from the client. In Warp, this is all done at the conduit level. As mentioned, the incoming data is represented as a <code>Source</code>. As part of that <code>Source</code>, every time a new chunk of data is received, the timeout handler is teased. Since teasing the handler is such a cheap operation (essentially just a memory write), Slowloris protection does not hinder the performance of individual connection handlers in a significant way.</p>

<h2 id="http-response-composer"><span class="caps">HTTP</span> Response Composer</h2>

<p>This section describes the <span class="caps">HTTP</span> response composer of Warp. A <span class="caps">WAI</span> <code>Response</code> has three constructors:</p>

<pre><code>ResponseFile Status ResponseHeaders FilePath (Maybe FilePart)
ResponseBuilder Status ResponseHeaders Builder
ResponseSource Status ResponseHeaders (Source (ResourceT IO) (Flush Builder))</code></pre>

<p><code>ResponseFile</code> is used to send a static file while <code>ResponseBuilder</code> and <code>ResponseSource</code> are for sending dynamic contents created in memory. Each constructor includes both <code>Status</code> and <code>ResponseHeaders</code>. <code>ResponseHeaders</code> is defined as a list of key/value header pairs.</p>

<h3 id="composer-for-http-response-header">Composer for <span class="caps">HTTP</span> Response Header</h3>

<p><a name="sec.warp.composer"> </a></p>

<p>The old composer built <span class="caps">HTTP</span> response header with a <code>Builder</code>, a rope-like data structure. First, it converted <code>Status</code> and each element of <code>ResponseHeaders</code> into a <code>Builder</code>. Each conversion runs in O(1). Then, it concatenates them by repeatedly appending one <code>Builder</code> to another. Thanks to the properties of <code>Builder</code>, each append operation also runs in O(1). Lastly, it packs an <span class="caps">HTTP</span> response header by copying data from <code>Builder</code> to a buffer in O(N).</p>

<p>In many cases, the performance of <code>Builder</code> is sufficient. But we experienced that it is not fast enough for high-performance servers. To eliminate the overhead of <code>Builder</code>, we implemented a special composer for <span class="caps">HTTP</span> response headers by directly using <code>memcpy()</code>, a highly tuned byte copy function in C.</p>

<h3 id="composer-for-http-response-body">Composer for <span class="caps">HTTP</span> Response Body</h3>

<p>For <code>ResponseBuilder</code> and <code>ResponseSource</code>, the <code>Builder</code> values provided by the application are packed into a list of <code>ByteString</code>. A composed header is prepended to the list and <code>send()</code> is used to send the list in a fixed buffer.</p>

<p>For <code>ResponseFile</code>, Warp uses <code>send()</code> and <code>sendfile()</code> to send an <span class="caps">HTTP</span> response header and body, respectively. <a href="#figure-11.7">Figure 11.7</a> illustrates this case. Again, <code>open()</code>, <code>stat()</code>, <code>close()</code> and other system calls can be omitted thanks to the cache mechanism described in <a href="#sec.warp.timers">Timers for File Descriptors</a>. The following subsection describes another performance tuning in the case of <code>ResponseFile</code>.</p>

<h3 id="sending-the-header-and-body-together">Sending the Header and Body Together</h3>

<p>When we measured the performance of Warp to send static files, we always did it with high concurrency (multiple connections at the same time) and achieved good results. However, when we set the concurrency value to 1, we found Warp to be really slow.</p>

<p>Observing the results of the <code>tcpdump</code> command, we realized that this is because originally Warp used the combination of <code>writev()</code> for header and <code>sendfile()</code> for body. In this case, an <span class="caps">HTTP</span> header and body are sent in separate <span class="caps">TCP</span> packets (<a href="#figure-11.11">Figure 11.11</a>).</p>

<div class="center figure">
<a name="figure-11.11"></a><img src="warp-images/tcpdump.png" alt="Figure 11.11 - Packet sequence of old Warp" title="Figure 11.11 - Packet sequence of old Warp" />
</div>

<p class="center figcaption">
<small>Figure 11.11 - Packet sequence of old Warp</small>
</p>

<p>To send them in a single <span class="caps">TCP</span> packet (when possible), new Warp switched from <code>writev()</code> to <code>send()</code>. It uses <code>send()</code> with the <code>MSG_MORE</code> flag to store a header and <code>sendfile()</code> to send both the stored header and a file. This made the throughput at least 100 times faster according to our throughput benchmark.</p>

<h2 id="clean-up-with-timers">Clean-up with Timers</h2>

<p>This section explain how to implement connection timeout and how to cache file descriptors.</p>

<h3 id="timers-for-connections">Timers for Connections</h3>

<p><a name="sec.warp.connectiontimers"> </a></p>

<p>To prevent Slowloris attacks, communication with a client should be canceled if the client does not send a significant amount of data for a certain period. Haskell provides a standard function called <code>timeout</code> whose type is as follows:</p>

<pre><code>Int -&gt; IO a -&gt; IO (Maybe a)</code></pre>

<p>The first argument is the duration of the timeout, in microseconds. The second argument is an action which handles input/output (<code>IO</code>). This function returns a value of <code>Maybe a</code> in the <code>IO</code> context. <code>Maybe</code> is defined as follows:</p>

<pre><code>data Maybe a = Nothing | Just a</code></pre>

<p><code>Nothing</code> indicates an error (with no reason specified) and <code>Just</code> encloses a successful value <code>a</code>. So, <code>timeout</code> returns <code>Nothing</code> if an action is not completed in a specified time. Otherwise, a successful value is returned wrapped with <code>Just</code>. The <code>timeout</code> function eloquently shows how great Haskell's composability is.</p>

<p><code>timeout</code> is useful for many purposes, but its performance is inadequate for implementing high-performance servers. The problem is that for each timeout created, this function will spawn a new user thread. While user threads are cheaper than system threads, they still involve an overhead which can add up. We need to avoid the creation of a user thread for each connection's timeout handling. So, we implemented a timeout system which uses only one user thread, called the timeout manager, to handle the timeouts of all connections. At its core are the following two ideas:</p>

<ul>
<li>double <code>IORef</code>s</li>
<li>safe swap and merge algorithm</li>
</ul>

<p>Suppose that status of connections is described as <code>Active</code> and <code>Inactive</code>. To clean up inactive connections, the timeout manager repeatedly inspects the status of each connection. If status is <code>Active</code>, the timeout manager turns it to <code>Inactive</code>. If <code>Inactive</code>, the timeout manager kills its associated user thread.</p>

<p>Each status is referred to by an <code>IORef</code>. <code>IORef</code> is a reference whose value can be destructively updated. In addition to the timeout manager, each user thread repeatedly turns its status to <code>Active</code> through its own <code>IORef</code> as its connection actively continues.</p>

<p>The timeout manager uses a list of the <code>IORef</code> to these statuses. A user thread spawned for a new connection tries to prepend its new <code>IORef</code> for an <code>Active</code> status to the list. So, the list is a critical section and we need atomicity to keep the list consistent.</p>

<div class="center figure">
<a name="figure-11.12"></a><img src="warp-images/timeout.png" alt="Figure 11.12 - A list of status values. \code{A} and \code{I} indicates \code{Active} and \code{Inactive}, respectively" title="Figure 11.12 - A list of status values. \code{A} and \code{I} indicates \code{Active} and \code{Inactive}, respectively" />
</div>

<p class="center figcaption">
<small>Figure 11.12 - A list of status values.  and  indicates  and , respectively</small>
</p>

<p>A standard way to keep consistency in Haskell is <code>MVar</code>. But <code>MVar</code> is slow, since each <code>MVar</code> is protected with a home-brewed lock. Instead, we used another <code>IORef</code> to refer to the list and <code>atomicModifyIORef</code> to manipulate it. <code>atomicModifyIORef</code> is a function for atomically updating an <code>IORef</code>&#8216;s values. It is implemented via <span class="caps">CAS</span> (Compare-and-Swap), which is much faster than locks.</p>

<p>The following is the outline of the safe swap and merge algorithm:</p>

<pre><code>do xs &lt;- atomicModifyIORef ref (\ys -&gt; ([], ys)) -- swap with an empty list, []
   xs&#39; &lt;- manipulates_status xs
   atomicModifyIORef ref (\ys -&gt; (merge xs&#39; ys, ()))</code></pre>

<p>The timeout manager atomically swaps the list with an empty list. Then it manipulates the list by toggling thread status or removing unnecessary status for killed user threads. During this process, new connections may be created and their status values are inserted via <code>atomicModifyIORef</code> by their corresponding user threads. Then, the timeout manager atomically merges the pruned list and the new list. Thanks to the lazy evaluation of Haskell, the application of the merge function is done in O(1) and the merge operation, which is in O(N), is postponed until its values are actually consumed.</p>

<h3 id="timers-for-file-descriptors">Timers for File Descriptors</h3>

<p><a name="sec.warp.timers"> </a></p>

<p>Let's consider the case where Warp sends the entire file by <code>sendfile()</code>. Unfortunately, we need to call <code>stat()</code> to know the size of the file because <code>sendfile()</code> on Linux requires the caller to specify how many bytes to be sent (<code>sendfile()</code> on FreeBSD/MacOS has a magic number <em>0</em> which indicates the end of file).</p>

<p>If <span class="caps">WAI</span> applications know the file size, Warp can avoid <code>stat()</code>. It is easy for <span class="caps">WAI</span> applications to cache file information such as size and modification time. If the cache timeout is fast enough (say 10 seconds), the risk of cache inconsistency is not serious. Because we can safely clean up the cache, we don't have to worry about leakage.</p>

<p>Since <code>sendfile()</code> requires a file descriptor, the naive sequence to send a file is <code>open()</code>, <code>sendfile()</code> repeatedly if necessary, and <code>close()</code>. In this subsection, we consider how to cache file descriptors to avoid calling <code>open()</code> and <code>close()</code> more than is necessary. Caching file descriptors should work as follows: if a client requests that a file be sent, a file descriptor is opened by <code>open()</code>. And if another client requests the same file shortly thereafter, the previously opened file descriptor is reused. At a later time, the file descriptor is closed by <code>close()</code> if no user thread uses it.</p>

<p>A typical tactic for this case is reference counting. We were not sure that we could implement a robust reference counter. What happens if a user thread is killed for unexpected reasons? If we fail to decrement its reference counter, the file descriptor leaks. We noticed that the connection timeout scheme is safe to reuse as a cache mechanism for file descriptors because it does not use reference counters. However, we cannot simply reuse the timeout manager for several reasons.</p>

<p>Each user thread has its own status–status is not shared. But we would like to cache file descriptors to avoid <code>open()</code> and <code>close()</code> by sharing. So, we need to search for the file descriptor for a requested file in a collection of cached file descriptors. Since this search should be fast, we should not use a list. Because requests are received concurrently, two or more file descriptors for the same file may be opened. Thus, we need to store multiple file descriptors for a single file name. The data structure we are describing is called a <em>multimap</em>.</p>

<p>We implemented a multimap whose look-up is O(log N) and pruning is O(N) with red-black trees whose nodes contain non-empty lists. Since a red-black tree is a binary search tree, look-up is O(log(N)) where N is the number of nodes. We can also translate it into an ordered list in O(N). In our implementation, pruning nodes which contain a file descriptor to be closed is also done during this step. We adopted an algorithm to convert an ordered list to a red-black tree in O(N).</p>

<h2 id="future-work">Future Work</h2>

<p>We have several ideas for improvement of Warp in the future, but we will only explain two here.</p>

<h3 id="memory-allocation">Memory Allocation</h3>

<p><a name="sec.warp.memory"> </a></p>

<p>When receiving and sending packets, buffers are allocated. These buffers are allocated as "pinned" byte arrays, so that they can be passed to C procedures like <code>recv()</code> and <code>send()</code>. Since it is best to receive or send as much data as possible in each system call, these buffers are moderately sized. Unfortunately, <span class="caps">GHC</span>'s method for allocating large (larger than 409 bytes in 64 bit machines) pinned byte arrays takes a global lock in the run-time system. This lock may become a bottleneck when scaling beyond 16 cores, if each core user thread frequently allocates such buffers.</p>

<p>We performed an initial investigation of the performance impact of large pinned array allocation for <span class="caps">HTTP</span> response header generation. For this purpose, <span class="caps">GHC</span> provides <code>eventlog</code> which can record timestamps of each event. We surrounded a memory allocation function with the function to record a user event. Then we compiled <code>mighty</code> with it and recorded the eventlog. The resulting eventlog is illustrated as follows:</p>

<div class="center figure">
<a name="figure-11.13"></a><img src="warp-images/eventlog.png" alt="Figure 11.13 - Eventlog" title="Figure 11.13 - Eventlog" />
</div>

<p class="center figcaption">
<small>Figure 11.13 - Eventlog</small>
</p>

<p>Brick red bars indicate the event created by us. So, the area surrounded by two bars is the time consumed by memory allocation. It is about 1/10 of an <span class="caps">HTTP</span> session. We are discussing how to implement memory allocation without locks.</p>

<h3 id="new-thundering-herd">New Thundering Herd</h3>

<p>The thundering herd problem is an "old-but-new" problem. Suppose that processes or native threads are pre-forked to share a listening socket. They call <code>accept()</code> on the socket. When a connection is created, old Linux and FreeBSD implementations wake up all of the processes or threads. Only one of them can accept it and the others sleep again. Since this causes many context switches, we face a performance problem. This is called the <em>thundering herd</em>. Recent Linux and FreeBSD implementations wake up only one process or native thread, making this problem a thing of the past.</p>

<p>Recent network servers tend to use the <code>epoll</code> family. If workers share a listening socket and they manipulate connections through the <code>epoll</code> family, thundering herd appears again. This is because the convention of the <code>epoll</code> family is to notify all processes or native threads. <code>nginx</code> and <code>mighty</code> are victims of this new thundering herd.</p>

<p>The parallel I/O manager is free from the new thundering herd problem. In this architecture, only one I/O manager accepts new connections through the <code>epoll</code> family. And other I/O managers handle established connections.</p>

<h2 id="conclusion">Conclusion</h2>

<p>Warp is a versatile web server library, providing efficient <span class="caps">HTTP</span> communication for a wide range of use cases. In order to achieve its high performance, optimizations have been performed at many levels, including network communications, thread management, and request parsing.</p>

<p>Haskell has proven to be an amazing language for writing such a code base. Features like immutability by default make it easier to write thread-safe code and avoid extra buffer copying. The multi-threaded run time drastically simplifies the process of writing event-driven code. And <span class="caps">GHC</span>'s powerful optimizations mean that in many cases, we can write high-level code and still reap the benefits of high performance. Yet with all of this performance, our code base is still relatively tiny (/under 1300 <span class="caps">SLOC</span> at time of writing). If you are looking to write maintainable, efficient, concurrent code, Haskell should be a strong consideration.</p>

  </body>
</html>
